package Trie;

import java.util.LinkedList;
import java.util.TreeMap;

class TrieNode {
    boolean over;
    String key;
    String value;
    TreeMap<Character,TrieNode> Children;
    public TrieNode(){
        over = false;
        key = null;
        value = null;
        Children = new TreeMap<>();
    }
}

public class Trie{
    private TrieNode root;
    public Trie(){
        root = new TrieNode();
        root.over = true;
    }

    public void insert(String key,String value){
        if(key == null || key.length() == 0){
            return ;
        }
        TrieNode node = root;
        TrieNode tempNode;
        int len = key.length();
        for(int i = 0; i < len; ++i){
            Character c = key.charAt(i);
            tempNode = node.Children.get(c);
            if(tempNode == null){
                tempNode = new TrieNode();
                node.Children.put(c,tempNode);
            }
            node = tempNode;
        }
        if(!node.over){
            node.over = true;
            node.key = key;
            node.value = value;
        }
        return ;
    }
    public LinkedList<TrieNode> search(String key){
        LinkedList<TrieNode> list = new LinkedList<>();
        list = search(key,list);
        if(list == null){

        }
        return list;
    }
    public LinkedList<TrieNode> search(String key,LinkedList<TrieNode> list){
        if(key == null || key.length() == 0){
            System.out.println(1);
            return null;
        }
        TrieNode node = root;
        TrieNode tempNode;
        int len = key.length();
        for(int i = 0; i < len; ++i){
            Character c = key.charAt(i);
            tempNode = node.Children.get(c);
            if(tempNode == null){
                System.out.println(2);
                return null;
            }
            node = tempNode;
        }
        return fuzzySearch(node,list);
    }

    public LinkedList<TrieNode> fuzzySearch(TrieNode node, LinkedList<TrieNode> list){
        if(node == null){
            System.out.println(3);
            return list;
        }
        if(node.over){
            list.add(node);
        }
        for (TrieNode value : node.Children.values()) {
            if(list.size() < 5) {
                fuzzySearch(value, list);
            }
        }
        return list;
    }

    public void delete(String key){
        if(key == null || key.length() == 0) return ;
        TrieNode node = root;
        TrieNode tempNode;
        Character c = key.charAt(0);
        tempNode = node.Children.get(c);
        deleteNode(tempNode,key);
        return ;
    }
    public boolean deleteNode(TrieNode node,String key){
        if(node == null || key == null || key.length() == 0){
            return false;
        }
        if(key.length() == 1){
            if(node.over){
                node.over = false;
                if(node.Children.isEmpty()){
                    return true;
                }else{
                    return false;
                }
            }else{
                return false;
            }
        }
        Character c = key.charAt(1);
        boolean ok = deleteNode(node.Children.get(c),key.substring(1));
        if(ok){
            node.Children.remove(c);
            if(node.over){
                ok = false;
            }
        }
        return ok;
    }

    public static void main(String[] args) {
        Trie tre = new Trie();
        tre.insert("apple","苹果");
        tre.insert("applepp","苹果屁屁");
        tre.insert("app","app");
        tre.insert("appleap","苹果a屁");
        tre.insert("applebp","苹果b屁");
        tre.insert("applecp","苹果c屁");
        tre.insert("appledp","苹果d屁");
        tre.insert("appleep","苹果e屁");
        tre.insert("banana","香蕉");
        tre.insert("cola","可乐");
        tre.search("apple");
        tre.delete("appleap");
        tre.search("a");
    }
}
